<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 打家劫舍III题：
         * 输入：nums = [3,2,3,null,3,null,1]
         * 输出：7
         * 解释：小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
         * 
         * 输入: root = [3,4,5,1,3,null,1]
         * 输出: 9
         * 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
         * 思路：区别：首位连接成环，首尾不能同时去打劫
         * 
        */
        /* 
            时间：O(2 ^ n)：最差情况，二叉树变成单链表，然后每个节点可能会被重复计算，达到2 ^ n，n是节点个数
            空间：O(n)：是递归栈调用的深度，是二叉树的高度
        */
        function TreeNode(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        let a = new TreeNode(3)
        let b = new TreeNode(2)
        let c = new TreeNode(3)
        let d = new TreeNode(null)
        let e = new TreeNode(3)
        let f = new TreeNode(null)
        let g = new TreeNode(1)
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g
        var rob = function(root) {
            if (!root) return 0
            // 左右是null，直接返回root.val就可以了，也不存在孙子了
            if (root.left === null && root.right === null) return root.val

            // 偷父节点，考虑左右的孙子
            let val1 = root.val
            if (root.left) val1 += rob(root.left.left) + rob(root.left.right)
            if (root.right) val1 += rob(root.right.left) + rob(root.right.right)

            // 不偷父节点，考虑左右儿子
            let val2 = rob(root.left) + rob(root.right)

            return Math.max(val1, val2)
        };
        // console.log(rob([2, 1, 1, 2]));
        // console.log(rob([2, 7, 9, 3, 1]));
        console.log(rob(a));
    </script>
</body>

</html>